class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()<=0)
            return 0;
        
        int maxarea=0;
        stack<int> higher;
        higher.push(-1);
        //[6, 7, 5, 2, 4, 5, 9, 3]
        for(int i=0;i<heights.size();++i)
        {
            while(higher.top()!=-1&&heights[higher.top()]>=heights[i])
            {      
                int index=higher.top();
                higher.pop();
                int area=heights[index]*(i-higher.top()-1);
                maxarea=max(maxarea,area); 
                //printf("%d,%d,%d,%d\n",i,index,area,maxarea);
                
            }
            higher.push(i);
        }
        while(higher.top()!=-1)
        {
            int index=higher.top();
            higher.pop();
            int area=heights[index] * (heights.size() - higher.top()-1);
            maxarea=max(maxarea,area); 
            //printf("%d,%d,%d\n",index,area,maxarea);
            
        }
        return maxarea;   
    }
};